pith. sign in

arxiv: 2606.25168 · v1 · pith:2KNXJUYGnew · submitted 2026-06-23 · 🧮 math.CO

Star Coloring on Some Subclasses of Chordal Graphs

Germ\'an Ben\'itez-Bobadilla , Fernando Esteban Contreras-Mendoza , C\'esar Hern\'andez-Cruz , Cl\'audia Linhares Sales , Ana Trujillo-Negrete This is my paper

Pith reviewed 2026-06-25 22:20 UTC · model grok-4.3

classification 🧮 math.CO
keywords star coloringchordal graphssplit graphsforbidden subgraphslinear-time recognition2-trees2-pathsstar chromatic number
0
0 comments X

The pith

A structural characterization together with forbidden induced subgraphs recognizes exactly which chordal graphs are star 3-colorable in linear time.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes both a structural characterization and a forbidden-subgraph characterization for which chordal graphs have star chromatic number at most 3. These descriptions directly produce a simple certifying algorithm that decides the property in linear time. Similar finite forbidden-subgraph lists are given for split graphs that are star 4-colorable or star 5-colorable. The work also determines the star chromatic numbers of 2-paths and exhibits a 2-tree requiring 6 colors.

Core claim

Star 3-colorable chordal graphs are exactly those without certain forbidden induced subgraphs and satisfying a corresponding structural property; the same approach yields finite forbidden-subgraph characterizations for star-4-colorable split graphs and for star-5-colorable split graphs; every 2-path is star 5-colorable while the star-4-colorable 2-paths are characterized by forbidden subgraphs; there exists a 2-tree on 21 vertices whose star chromatic number is 6 while every proper induced subgraph has star chromatic number 5.

What carries the argument

The collection of forbidden induced subgraphs for star 3-colorable chordal graphs, which together with the structural characterization partitions the class.

If this is right

  • Star 3-colorability of chordal graphs can be decided by a certifying algorithm in linear time.
  • Star 4-colorability and star 5-colorability of split graphs each admit linear-time certifying recognition via finite forbidden induced subgraphs.
  • Every 2-path has star chromatic number at most 5, with equality for some instances that avoid the forbidden subgraphs for 4 colors.
  • A 2-tree on 21 vertices requires 6 colors for star coloring, while all its proper induced subgraphs require only 5.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The linear-time recognition may be useful for practical graph coloring applications on chordal graphs arising in optimization.
  • Similar forbidden-subgraph techniques could be applied to other coloring variants on chordal graphs.
  • The example 2-tree indicates that star chromatic number grows with the size of 2-trees even though treewidth remains 2.
  • The characterizations separate the decision problem from the search for an actual coloring.

Load-bearing premise

The listed forbidden induced subgraphs and the structural characterization together include all star-3-colorable chordal graphs and exclude all others without exception or overlap.

What would settle it

A chordal graph that is star 3-colorable yet contains one of the listed forbidden subgraphs, or a chordal graph with star chromatic number greater than 3 that matches the structural description.

Figures

Figures reproduced from arXiv: 2606.25168 by Ana Trujillo-Negrete, C\'esar Hern\'andez-Cruz, Cl\'audia Linhares Sales, Fernando Esteban Contreras-Mendoza, Germ\'an Ben\'itez-Bobadilla.

Figure 1
Figure 1. Figure 1: Six minimal obstructions to star 3-colorability in chordal graphs. In the first row, from left to right, we have the graphs K4, kite, gem, and X127; in the second row the graphs D4 and D5 are depicted. Let k be a positive integer. The k-centipede (also known as k-comb) is the graph with vertex set {ui} k i=1 ∪ {vi} k i=1 and with edge set {uivi} k i=1 ∪ {uiui+1 : i ∈ {1, . . . , k −1}}. In other words, the… view at source ↗
Figure 2
Figure 2. Figure 2: Star 3-colorings of all induced subgraphs obtained, up to isomorphism, by deleting a single vertex from K4, kite, gem, X127 and D4. These colorings show that every proper induced subgraph of these graphs is star 3-colorable. Together with Lemma 2.1 (which proves the minimality of the graphs Di for i ≥ 4), this implies that every graph in F ch 3 is a minimal obstruction to star 3-colorability in chordal gra… view at source ↗
Figure 3
Figure 3. Figure 3: Left: the configuration described in item (iii) of Proposition [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Minimal obstructions to star 4-coloring in split graphs. Proposition 3.9. If G is a split graph, then G is star 4-colorable if and only if G is F sp 4 -free. Proof. Let G be a split graph with split partition (K, S). Since each element of F sp 4 is a minimal obstruction to star 4-coloring, it follows that if G is star 4-colorable, then G is F sp 4 -free. Now, suppose that G is F sp 4 -free. To prove that G… view at source ↗
Figure 5
Figure 5. Figure 5: a. Case 2. |S1| = 1. Let x0 be the unique vertex in S1. Suppose, without loss of generality, that x0 is adjacent to 0. Since the family of neighborhoods is an antichain, and N(S) = K, we have that 2 ≤ |S \ {x0}| ≤ 3, otherwise G is isomorphic to G1. Moreover, if |S \ {x0}| = 3, then G is isomorphic to G5. Suppose that S \ {x0} = {x1, x2}. Since the family of neighborhoods is an antichain, and there is no v… view at source ↗
Figure 6
Figure 6. Figure 6: Minimal obstructions to star 5-coloring in split graphs. Lemma 3.11. Every graph in F sp 5 is a minimal obstruction to star 5-colorability. Proof. For every i ∈ {1, 2, 3, 5, 6, 9, 12}, the graph Ji can be obtained by adding a true twin to G1, G2, G3, or G5, whereas K6, J4, and J8 can be obtained by adding a universal vertex to K5, G3, and G5, respectively. By Propositions 3.6 and 3.8, K6 and Ji are minimal… view at source ↗
Figure 7
Figure 7. Figure 7: Star 5-colorings of each subgraph of J7, J10 or J11 obtained by deleting a vertex of the set S. From top to bottom, the rows correspond to J7, J10 and J11, respectively; in each drawing the grey vertex (and its incident grey edges) indicates the deleted vertex. belongs to S. Hence, Ji is a minimal obstruction to star 5-colorability, for every i ∈ {7, 10, 11}. Therefore, every graph in F sp 5 is a minimal o… view at source ↗
Figure 8
Figure 8. Figure 8: Cases 1 and 2 of Proposition 3.12. Case 2. Suppose |N(S3)| = 4. Without loss of generality assume that K \ N(S3) = {4}, and let y ∈ S \ S3 be such that 4 ∈ N(y), so y ∈ S1 ∪ S2. Let x1, x2 ∈ S3. By property (2) we can assume without loss of generality that N(x1) = {0, 1, 2} and N(x2) = {0, 1, 3}. We claim that |S3| = 2. Otherwise, let x3 be another vertex in S3. Since S satisfies the antichain condition, N… view at source ↗
Figure 9
Figure 9. Figure 9: Case 3 of Proposition 3.12 [PITH_FULL_IMAGE:figures/full_fig_p019_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Case 4 when S1 ̸= ∅ of Proposition 3.12. 3.2. Suppose that exactly one of y and w belongs to S1. Without loss of generality, assume S1 = {y}, and w ∈ S2. Since S satisfies the antichain condition, any vertex z ∈ S2 must satisfy N(z) = {i, 3}, for some i ∈ {0, 1, 2}. Figure 9b depicts a star 5-coloring of G when |S2| = 3; the cases when |S2| ≤ 2 are easy consequences of this case. 3.3. If cases 3.1 and 3.2… view at source ↗
Figure 11
Figure 11. Figure 11: Cases 4.1 and 4.2 of Proposition 3.12. As with star 4-colorings, we are now able to propose a certifying recognition algorithm for split graphs having star chromatic number at most 5. Corollary 3.13. There is a certifying algorithm that runs in time O(|V | + |E|) to test whether an input split graph G has a star 5-coloring. Proof sketch. The proof is analogous to that of Corollary 3.10. The idea is to obt… view at source ↗
Figure 12
Figure 12. Figure 12: A 2-path G and its base graph BG, which is a caterpillar with spine (u1, u2, u3, u4). Hence, two 2-paths with the same associated degree sequence have isomorphic base caterpillars and the same forced fan overlaps, and therefore are isomorphic. If σ(G) is the reversal of σ(G′ ), then the same argument applies after reversing the canonical construction of one of the graphs. Hence G ∼= G′ in this case as wel… view at source ↗
Figure 13
Figure 13. Figure 13: The two minimal 2-paths that are not star 4-colorable. Lemma 4.3. Let G be a 2-path, and let F1, . . . , Ft be the fans associated with the vertices of the spine of BG as above. If P is an induced path on four vertices in G, then there exists i ∈ [t] such that |V (P) ∩ V (Fi)| ≥ 3. Proof. It is enough to prove that every induced path on three vertices in G is contained in some fan Fi . Indeed, if P = (w, … view at source ↗
Figure 14
Figure 14. Figure 14: star 4-colorings of all induced subgraphs obtained, up to isomorphism, by deleting one vertex from each of the two 2-paths H1 and H2. These colorings show that every proper induced subgraph of H1 and H2 is star 4-colorable, and hence H1 and H2 are minimal obstructions to star 4-colorability in the class of 2-paths. purple, but then u7 must be assigned blue. Therefore, (u7, u2, u3, u5) is a bicolored P4, a… view at source ↗
Figure 15
Figure 15. Figure 15: A star 4-coloring of G given by the coloring c defined in Subsection 4.3. The caterpillar BG is highlighted in gray. Vertex labels encode the colors, with 1 = red, 2 = blue, 3 = green, and 4 = purple. Proof. Let F1, . . . , Ft be the maximal fans of G. We first show that c is proper. It is enough to prove that the restriction of c to each fan Fi is proper. For i = 1 this follows directly from the definiti… view at source ↗
Figure 16
Figure 16. Figure 16: Three minimal obstructions to star 4-colorability within the class of partial 2-paths. We show that none of these possibilities can be extended to the vertex z ∈ V (Fi+1) \ V (Fi). Case 1. Suppose (w, x, y) = (vi,0, vi,1, vi,2). Since z is adjacent to y = vi,2 and lies outside Fi , the vertex vi,2 must be one of the vertices through which Fi meets Fi+1. This is possible only if di = 2, in which case vi,2 … view at source ↗
Figure 17
Figure 17. Figure 17: A 2-path G together with its base caterpillar BG (drawn with thicker edges). The labelled vertices u1, . . . , u12 form the spine of BG and are the centres of the maximal fans F1, . . . , F12 of G. The vertex colors illustrate the star 5-coloring c defined in Subsection 4.4. – If t ≥ i + 1 and di+1 = 2, we set c(vi,j ) = c(vi,j−3) for 3 ≤ j ≤ di , and c(vi,di+1) = the unique color not used on {ui , vi,0, … view at source ↗
Figure 18
Figure 18. Figure 18: The 2-tree H from Proposition 4.11 together with a star 6-coloring. be a star 5-coloring. Without loss of generality, assume c(x0) = red. For i ∈ {1, 2, 3, 4} set Yi := {yi,1, yi,2, yi,3, yi,4}. Clearly, for each i ∈ {1, 2, 3, 4} no vertex of Yi receives the color c(xi), since xi is adjacent to every vertex in Yi . Case 1. There exist indices 1 ≤ i < j ≤ 4 such that c(xi) = c(xj ). Among all such pairs ch… view at source ↗
Figure 19
Figure 19. Figure 19: Maximal proper subgraphs of H used in the proof of Proposition 4.11. The three graphs in the top row show explicit star 5-colorings of H − x0, H − x1 and H − x2 (up to symmetry). The two graphs in the bottom row display partial star 5-colorings of H − y1,r and H − y2,r; the remaining uncolored vertices in the corresponding fans are then colored with two colors as specified in the proof. Acknowledgements G… view at source ↗
read the original abstract

A star coloring of a graph $G$ is a proper coloring in which no path on four vertices is bicolored. The star chromatic number $\chi_{\star}(G)$ is the minimum number of colors in a star coloring of $G$. In this work we study star colorings from the perspective of forbidden induced subgraphs, focusing on three subclasses of chordal graphs. We provide both a structural characterization and a characterization in terms of forbidden induced subgraphs for star $3$-colorable chordal graphs; such characterizations yield a simple certifying recognition algorithm, running in time $O(|V|+|E|)$, for this class. We also characterize split graphs that are star $4$-colorable and star $5$-colorable in terms of (finitely many) forbidden induced subgraphs, again deriving linear-time certifying recognition algorithms. Finally, we study star colorings of $2$-trees and $2$-paths: we characterize the $2$-paths that are star $4$-colorable, prove that every $2$-path is star $5$-colorable, and exhibit a $2$-tree on $21$ vertices with star chromatic number $6$ such that any proper induced subgrahp has star chromatic number $5$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 0 minor

Summary. The paper provides both a structural characterization and a characterization in terms of forbidden induced subgraphs for star 3-colorable chordal graphs, yielding a simple certifying recognition algorithm running in O(|V|+|E|) time. It also characterizes split graphs that are star 4-colorable and star 5-colorable via (finitely many) forbidden induced subgraphs, again with linear-time certifying algorithms. For 2-trees and 2-paths, the paper characterizes the 2-paths that are star 4-colorable, proves every 2-path is star 5-colorable, and exhibits a 2-tree on 21 vertices with star chromatic number 6 such that every proper induced subgraph has star chromatic number 5.

Significance. If the characterizations are correct and complete, the work supplies efficient recognition procedures for star colorability in these chordal subclasses, which is a concrete algorithmic contribution. The explicit 2-tree example with χ*=6 (and the hereditary property noted) is a useful concrete datum for bounding star chromatic numbers in treewidth-2 graphs. The stress-test concern about unexamined derivations does not fully land on the full manuscript, as the abstract is expected to omit proofs and lists; however, the absence of any verification data or explicit lists even in summary form leaves the partition claim untestable from the given information.

major comments (2)
  1. Abstract: the central claim that the (unspecified) forbidden induced subgraphs together with the structural description exactly partition chordal graphs into star-3-colorable and non-colorable instances (with no missing cases or overlaps) is load-bearing for both the characterization and the linear-time algorithm; without the explicit list or a completeness argument, the claim cannot be assessed.
  2. Abstract: the assertion of an O(|V|+|E|) certifying recognition algorithm is stated as a direct corollary, but no description of the certification mechanism (e.g., how the forbidden-subgraph check produces a certificate) is supplied, making the complexity claim unverified.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful review of the manuscript. The major comments focus on the abstract; the full characterizations, proofs, and algorithmic details appear in the body of the paper as described below.

read point-by-point responses

  1. Referee: Abstract: the central claim that the (unspecified) forbidden induced subgraphs together with the structural description exactly partition chordal graphs into star-3-colorable and non-colorable instances (with no missing cases or overlaps) is load-bearing for both the characterization and the linear-time algorithm; without the explicit list or a completeness argument, the claim cannot be assessed.

    Authors: The abstract is a high-level summary. Section 3 of the manuscript gives the explicit finite list of forbidden induced subgraphs for star-3-colorable chordal graphs, the structural characterization, and the completeness proof. The proof shows that a chordal graph is star-3-colorable if and only if it avoids the listed subgraphs and satisfies the structural conditions, with no missing cases or overlaps; both directions are established by explicit constructions and case analysis. revision: no

  2. Referee: Abstract: the assertion of an O(|V|+|E|) certifying recognition algorithm is stated as a direct corollary, but no description of the certification mechanism (e.g., how the forbidden-subgraph check produces a certificate) is supplied, making the complexity claim unverified.

    Authors: The manuscript derives the linear-time certifying algorithm directly from the characterizations in Section 3: forbidden-subgraph detection for a fixed finite set runs in O(|V|+|E|) time, and the structural description yields an explicit star coloring when the graph is colorable. The certificate is either the coloring (constructible in linear time) or the discovered forbidden subgraph. These steps are spelled out following the characterizations. revision: no

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper derives structural and forbidden-subgraph characterizations for star-3-colorable chordal graphs, plus similar results for split graphs and 2-paths/2-trees, directly from the definitions of star coloring and chordal graphs. These are standard combinatorial case analyses and minimal-obstruction arguments with no equations, fitted parameters, or self-referential quantities; the linear-time recognition algorithms follow immediately as corollaries of the characterizations being checkable. No load-bearing step reduces to a prior result by the same authors or to an input by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper rests entirely on standard definitions of chordal graphs, split graphs, 2-trees, 2-paths, and star coloring; no numerical parameters are fitted and no new entities are postulated.

axioms (1)
  • standard math Standard definitions and basic properties of chordal graphs, split graphs, 2-trees, and star coloring hold.
    Invoked throughout the abstract as the foundation for the characterizations.

pith-pipeline@v0.9.1-grok · 5781 in / 1336 out tokens · 34857 ms · 2026-06-25T22:20:21.861492+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

16 extracted references

  1. [1]

    Albertson, Glenn G

    Michael O. Albertson, Glenn G. Chappell, Hal A. Kierstead, André Kündgen, and Radhika Ramamurthi. Coloring with no2-coloredP 4’s.The Electronic Journal of Combinatorics, 11:R26–R26, 2004

    2004

  2. [2]

    Acyclic, starandinjectivecolouring: AcomplexitypictureforH-freegraphs.Journal of Computer and System Sciences, 154:103662, 2025

    Jan Bok, Nikola Jedličková, Barnaby Martin, Pascal Ochem, Daniël Paulusma, and Siani Smith. Acyclic, starandinjectivecolouring: AcomplexitypictureforH-freegraphs.Journal of Computer and System Sciences, 154:103662, 2025

    2025

  3. [3]

    Murty.Graph Theory, volume 244 ofGraduate Texts in Mathematics

    John Adrian Bondy and U.S.R. Murty.Graph Theory, volume 244 ofGraduate Texts in Mathematics. Springer London, London, 2008

    2008

  4. [4]

    Oleg V. Borodin. On acyclic colorings of planar graphs.Discrete Mathematics, 25(3):211– 236, 1979. 37

    1979

  5. [5]

    Kathie Cameron, Jan Goedgebeur, Shenwei Huang, and Yongtang Shi.k-Critical graphs inP 5-free graphs.Theoretical Computer Science, 864:80–91, 2021

    2021

  6. [6]

    House of graphs 2.0: A database of interesting graphs and more.Discrete Applied Mathematics, 325:97–107, 2023

    Kris Coolsaet, Stijn D’hondt, and Jan Goedgebeur. House of graphs 2.0: A database of interesting graphs and more.Discrete Applied Mathematics, 325:97–107, 2023

    2023

  7. [7]

    Star coloring of graphs.Journal of Graph Theory, 47(3):163–182, 2004

    Guillaume Fertin, André Raspaud, and Bruce Reed. Star coloring of graphs.Journal of Graph Theory, 47(3):163–182, 2004

    2004

  8. [8]

    Stéphane Foldes and Peter L. Hammer. Split graphs. InProceedings of the Eighth Southeast- ern Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1977), volume No. XIX ofCongress. Numer., pages 311–315. Utilitas Math., Winnipeg, MB, 1977

    1977

  9. [9]

    North Holland, 2004

    Martin Charles Golumbic.Algorithmic graph theory and perfect graphs 2nd Edition. North Holland, 2004

    2004

  10. [10]

    Acyclic colorings of planar graphs.Israel Journal of Mathematics, 14(4):390–408, 1973

    Branko Grünbaum. Acyclic colorings of planar graphs.Israel Journal of Mathematics, 14(4):390–408, 1973

    1973

  11. [11]

    Algorithm 447: efficient algorithms for graph manipu- lation.Commun

    John Hopcroft and Robert Tarjan. Algorithm 447: efficient algorithms for graph manipu- lation.Commun. ACM, 16(6):372–378, June 1973

    1973

  12. [12]

    Karthick

    T. Karthick. Star coloring of certain graph classes.Graphs and Combinatorics, 34(1):109– 128, 2018

    2018

  13. [13]

    On3-colorableP 5-free graphs.SIAM Journal on Discrete Mathematics, 26(4):1682–1708, 2012

    Frédéric Maffray and Grégory Morel. On3-colorableP 5-free graphs.SIAM Journal on Discrete Mathematics, 26(4):1682–1708, 2012

    2012

  14. [14]

    Graph formats, 2026

    Brendan McKay. Graph formats, 2026. Accesed: February 20th, 2026

    2026

  15. [15]

    McKay and Adolfo Piperno

    Brendan D. McKay and Adolfo Piperno. Practical graph isomorphism, II.Journal of Symbolic Computation, 60:94–112, 2014

    2014

  16. [16]

    Colorings and homomorphisms of minor closed classes

    Jaroslav Nešetřil and Patrice Ossona de Mendez. Colorings and homomorphisms of minor closed classes. In Boris Aronov, Saugata Basu, János Pach, and Micha Sharir, editors, Discrete and Computational Geometry: The Goodman-Pollack Festschrift, pages 651–664. Springer Berlin Heidelberg, Berlin, Heidelberg, 2003. A Split minimal obstructions to star 6-colorabi...

    2003