pith. sign in

arxiv: 1907.05018 · v2 · pith:4ULOWPA7new · submitted 2019-07-11 · 🧮 math.CO · cs.DM

Structural domination and coloring of some (P₇, C₇)-free graphs

S. A. Choudum , T. Karthick , Manoj M. Belavadi This is my paper

Pith reviewed 2026-05-24 23:22 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords induced subgraphssplit graphsdominationchromatic numberforbidden subgraphsP7-free graphsC7-free graphsgem-free graphs
0
0 comments X

The pith

A graph has every connected induced subgraph dominated by an induced connected split graph if and only if it avoids six specific induced subgraphs including P7 and C7.

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

The paper proves that a graph G satisfies the property that every connected induced subgraph is dominated by an induced connected split graph if and only if G is free of a set of six graphs, each containing an induced P5 and including P7 and C7. A parallel if-and-only-if characterization is given for domination by induced complete split graphs. Structural descriptions are then derived for the subclasses of (P7, C7, C4, gem)-free graphs and (P7, C7, C4, diamond)-free graphs, from which chromatic number bounds follow directly.

Core claim

The central claim is that every connected induced subgraph of a graph G is dominated by an induced connected split graph if and only if G is C-free, where C is a set of six graphs which includes P7 and C7, and each containing an induced P5. Structural descriptions are given for the class of (P7, C7, C4, gem)-free graphs and for the class of (P7, C7, C4, diamond)-free graphs. These yield that every (P7, C7, C4, gem)-free graph G satisfies χ(G) ≤ 2ω(G)−1, and every (P7, C7, C4, diamond)-free graph H satisfies χ(H) ≤ ω(H)+1, with both bounds tight for subgraphs of the Petersen graph containing a C5.

What carries the argument

The set C of six forbidden induced subgraphs that exactly marks the graphs in which every connected induced subgraph is dominated by an induced connected split graph.

If this is right

  • Every (P7, C7, C4, gem)-free graph G satisfies χ(G) ≤ 2ω(G)−1.
  • Every (P7, C7, C4, diamond)-free graph H satisfies χ(H) ≤ ω(H)+1.
  • Both upper bounds on chromatic number are tight for any subgraph of the Petersen graph containing a C5.
  • A similar forbidden-subgraph characterization holds for graphs in which every connected induced subgraph is dominated by an induced complete split graph.

Where Pith is reading between the lines

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

  • The forbidden-subgraph lists may support polynomial recognition procedures for the characterized classes.
  • The linear bounds suggest these graph classes are χ-bounded with small multiplicative or additive factors.
  • Parallel characterizations could be sought for other combinations of the six graphs with additional forbidden induced subgraphs.

Load-bearing premise

The structural descriptions of the (P7,C7,C4,gem)-free and (P7,C7,C4,diamond)-free classes are sufficiently detailed and accurate to directly imply the stated chromatic number bounds without requiring additional unstated restrictions.

What would settle it

A graph that avoids all six members of C yet has some connected induced subgraph not dominated by any induced connected split graph, or a (P7,C7,C4,gem)-free graph whose chromatic number exceeds 2 times its clique number.

Figures

Figures reproduced from arXiv: 1907.05018 by Manoj M. Belavadi, S. A. Choudum, T. Karthick.

Figure 1
Figure 1. Figure 1: Some special graphs Let Q1, Q2, Q3, Q4 and Q5 be five graphs as shown in [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
read the original abstract

We show that every connected induced subgraph of a graph $G$ is dominated by an induced connected split graph if and only if $G$ is $\cal{C}$-free, where $\cal{C}$ is a set of six graphs which includes $P_7$ and $C_7$, and each containing an induced $P_5$. A similar characterisation is shown for the class of graphs which are dominated by induced complete split graphs. Motivated by these results, we study structural descriptions of some classes of $\cal{C}$-free graphs. In particular, we give structural descriptions for the class of ($P_7$,$C_7$,$C_4$,gem)-free graphs and for the class of ($P_7$,$C_7$,$C_4$,diamond)-free graphs. Using these results, we show that every ($P_7$,$C_7$,$C_4$,gem)-free graph $G$ satisfies $\chi(G) \leq 2\omega(G)-1$, and that every ($P_7$,$C_7$,$C_4$,diamond)-free graph $H$ satisfies $\chi(H) \leq \omega(H)+1$. These two upper bounds are tight for any subgraph of the Petersen graph containing a $C_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

0 major / 3 minor

Summary. The paper proves that a graph G has the property that every connected induced subgraph is dominated by an induced connected split graph if and only if G is free of a specific set C of six graphs (each containing an induced P5 and including P7 and C7). An analogous characterization is given for domination by induced complete split graphs. Structural descriptions are then derived for the (P7,C7,C4,gem)-free graphs and the (P7,C7,C4,diamond)-free graphs. These are used to establish the bounds χ(G) ≤ 2ω(G)−1 for the former class and χ(H) ≤ ω(H)+1 for the latter, with both bounds shown to be tight on subgraphs of the Petersen graph that contain a C5.

Significance. If the characterizations and structural descriptions hold, the work supplies new forbidden-subgraph conditions under which domination by split graphs is guaranteed and yields explicit, tight chromatic-number bounds for two concrete subclasses. The results strengthen the literature on χ-boundedness for (P7,C7)-free graphs by linking structural domination directly to coloring inequalities, with the tightness examples providing concrete verification.

minor comments (3)
  1. The precise list of the six graphs in C (beyond the mention of P7 and C7) should be stated explicitly in the introduction or in a dedicated figure, rather than left to the reader to infer from later sections.
  2. In the structural descriptions of the (P7,C7,C4,gem)-free and (P7,C7,C4,diamond)-free classes, clarify whether the descriptions assume the graph is connected or apply componentwise; this affects the direct applicability of the χ-bounds.
  3. The proof that the Petersen subgraphs lie inside the respective classes (and attain the stated bounds) would benefit from an explicit verification that they avoid the additional forbidden subgraphs C4, gem, or diamond.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary of our results on forbidden-subgraph characterizations for split-graph domination and the derived chromatic bounds for the two (P7,C7)-free subclasses. The recommendation for minor revision is noted. No specific major comments appear in the report.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper establishes forbidden-subgraph characterizations (every connected induced subgraph dominated by an induced connected split graph iff C-free) and then provides explicit structural descriptions of the (P7,C7,C4,gem)-free and (P7,C7,C4,diamond)-free classes. From those descriptions it derives the stated chi bounds directly. No step reduces a claimed prediction or first-principles result to a fitted parameter, self-citation chain, or definitional tautology; the characterizations and structural decompositions are presented as independent combinatorial arguments whose validity can be checked against the forbidden-subgraph conditions without reference to the target chi inequalities. The tightness examples are external (subgraphs of the Petersen graph) and do not close any loop inside the derivation.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies exclusively on standard graph-theoretic definitions and techniques; no free parameters, ad-hoc axioms, or new entities are introduced.

axioms (1)
  • standard math Standard definitions and properties of induced subgraphs, domination, split graphs, chromatic number, and clique number from graph theory.
    These background facts are invoked throughout the characterizations and bounds.

pith-pipeline@v0.9.0 · 5784 in / 1352 out tokens · 31809 ms · 2026-05-24T23:22:52.012065+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages · 2 internal anchors

  1. [1]

    Addario-Berry, M

    L. Addario-Berry, M. Chudnovsky, F. Havet, B. Reed and P. Seymour, Bisimplicial vertices in even-hole-free graphs. Journal of Combinatorial Theory, Series B , 98 (2008) 1119–1164

    work page 2008

  2. [2]

    Bacs´ o, Complete description of forbidden subgraphs in the structural domina- tion problem

    G. Bacs´ o, Complete description of forbidden subgraphs in the structural domina- tion problem. Discrete mathematics 309 (2009) 2466–2472

    work page 2009

  3. [3]

    Bacs´ o, D

    G. Bacs´ o, D. Michalak and Zs. Tuza, Dominating bipartit e subgraphs in graphs. Discussiones Mathematicae Graph Theory 25 (2005) 85–94. 16

    work page 2005

  4. [4]

    Bacs´ o and Z

    G. Bacs´ o and Z. Tuza, Dominating cliques in P5-free graphs. Periodica Mathemat- ica Hungaria 21:4 (1990) 303–308

    work page 1990

  5. [5]

    Bacs´ o and Zs

    G. Bacs´ o and Zs. Tuza, Domination properties and induce d subgraphs. Discrete mathematics 111 (1993) 37–40

    work page 1993

  6. [6]

    Bacs´ o, Zs

    G. Bacs´ o, Zs. Tuza and M. Voigt, Characterisation of gra phs dominated by in- duced paths. Discrete mathematics 307 (2007) 822–826

    work page 2007

  7. [7]

    An Optimal $\chi$-Bound for ($P_6$, diamond)-Free Graphs

    K. Cameron, S. Huang and O. Merkel, An optimal χ-bound for ( P6, diamond)-free graphs. Available on: arXiv:1809.00739 [math.CO], (2018)

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  8. [8]

    The class of $(P_7,C_4,C_5)$-free graphs: decomposition, algorithms, and $\chi$-boundedness

    K. Cameron, S. Huang, I. Penev, and V. Sivaraman, The clas s of ( P7, C4, C5)- free graphs: decompositions, algorithms, and χ-boundedness. Available on: arXiv:1803.03315 [math.CO], (2018)

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  9. [9]

    S. A. Choudum, T. Karthick and M. A. Shalu, Perfect colori ng and linearly χ- bounded P6-free graphs. Journal of Graph Theory 54 (2007) 293–306

    work page 2007

  10. [10]

    Chudnovsky and V

    M. Chudnovsky and V. Sivaraman, Perfect divisibility a nd 2-divisibility. Journal of Graph Theory 90 (2019) 54–60

    work page 2019

  11. [11]

    M. B. Cozzens and L. L. Kelleher, Dominating cliques in g raphs. Discrete Mathe- matics 86 (1990) 101–116

    work page 1990

  12. [12]

    Dhanalakshmi, N

    S. Dhanalakshmi, N. Sadagopan and V. Manogna, On 2 K2-free graphs. Interna- tional Journal of Pure and Applied Mathematics 109 (2016) 167–173

    work page 2016

  13. [13]

    F¨ oldes and P

    S. F¨ oldes and P. L. Hammer. Split graphs, in: Proceedin gs of the Eighth South- eastern Conference on Combinatorics, Graph Theory and Comp uting, Congressus Numerantium XIX, Utilitas Math, Winnipeg, 1977, 311–315

    work page 1977

  14. [14]

    J. L. Fouquet, V. Giakoumakis, F. Maire, and H. Thuillie r, On graphs without P5 and P5. Discrete Mathematics 146 (1995) 33–44

    work page 1995

  15. [15]

    Gy´ arf´ as, Problems from the world surrounding perf ect graphs

    A. Gy´ arf´ as, Problems from the world surrounding perf ect graphs. Zastosowania Matematyki Applicationes Mathematicae 19 (1987) 413–441

    work page 1987

  16. [16]

    Karthick and F

    T. Karthick and F. Maffray, Square-free graphs with no si x-vertex induced path. SIAM Journal on Discrete Mathematics 33 (2019) 874–909

    work page 2019

  17. [17]

    S. L. Peng, Characterizing and recognizing probe block graphs. Theoretical Com- puter Science 568 (2015) 97–102

    work page 2015

  18. [18]

    Paulusma, A new characterization of P6-free graphs

    Pim van ’t Hof and D. Paulusma, A new characterization of P6-free graphs. Dis- crete Applied Mathematics 158 (2010) 731–740

    work page 2010

  19. [19]

    Schiermeyer and B

    I. Schiermeyer and B. Randerath. Polynomial χ-binding functions and forbidden induced subgraphs: A survey. Graphs and Combinatorics 35 (2019) 1–31

    work page 2019

  20. [20]

    D. B. West. Introduction to Graph Theory, 2nd Edition, P rentice-Hall, Englewood Cliffs, New Jersey, 2000

    work page 2000

  21. [21]

    E. S. Wolk. The comparability graph of a tree. Proceedings of the American Math- ematical Society 13 (1962) 789–795. 17

    work page 1962