Graphs with no induced C_ 4 and 2K_ 2

DOI10.1016/0012-365X(93)90477-BzbMATH Open0772.05082OpenAlexW179301118MaRDI QIDQ1801686FDOQ1801686

Authors Mihály Hujter, András Pluhár, Zsolt Tuza, Zoltán Blázsik 

Publication date 20 June 1993

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(93)90477-b

zbMATH Keywords

induced subgraphcliqueindependent setsplit graphsNordhaus-Gaddum theorem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Structural characterization of families of graphs (05C75)

Recommendations

• scientific article; zbMATH DE number 622475
• On graphs with no induced subdivision of \(K_4\)
• On graphs without a \(C_{4}\) or a diamond
• Maximal cliques in \(\{P_{2} \cup P_{3},C_{4}\}\)-free graphs
• On self-complementary chordal graphs

Cites Work

• scientific article; zbMATH DE number 3598234 (Why is no real title available?)
• scientific article; zbMATH DE number 4183452 (Why is no real title available?)
• A bound on the chromatic number of graphs without certain induced subgraphs
• Covering all cliques of a graph
• Covering the cliques of a graph with vertices
• On Complementary Graphs

Cited In (42)

• Maximal cliques in \(\{P_{2} \cup P_{3},C_{4}\}\)-free graphs
• Constrained Hitting Set and Steiner Tree in SCk and 2K2-free Graphs
• Chromatic bounds for the subclasses of \(pK_2\)-free graphs
• Vertex coloring of graphs with few obstructions
• Powers of ideals associated to \((C_{4},2K_{2})\)-free graphs
• Coloring of \((P_5, 4\)-wheel)-free graphs
• On the Lovász-Schrijver PSD-operator on graph classes defined by clique cutsets
• Extremal graphs for the list-coloring version of a theorem of Nordhaus and Gaddum
• Arbitrarily partitionable \(\{2K_2, C_4\}\)-free graphs
• On realization graphs of degree sequences
• Nonsplit Graphs with Split Maximal Induced Subgraphs
• On the chromatic number of \(2 K_2\)-free graphs
• On fractional realizations of graph degree sequences
• On the use of Boolean methods for the computation of the stability number
• Colouring of \((P_3 \cup P_2)\)-free graphs
• Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey
• Chromatic bounds for some classes of \(2 K_2\)-free graphs
• On the stable set problem in special \(P_{5}\)-free graphs
• A coloring algorithm for \(4 K_1\)-free line graphs
• Split graphs and Nordhaus-Gaddum graphs
• Stability in \(P_5\)- and banner-free graphs
• Recognition of split-graphic sequences
• Linear recognition of pseudo-split graphs
• Vizing bound for the chromatic number on some graph classes
• Graphs in which each \(C_4\) spans \(K_4\)
• Dynamically maintaining split graphs
• Star coloring of certain graph classes
• Star chromatic bounds
• On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
• Hereditary unigraphs and Erdős-Gallai equalities
• Near optimal colourability on hereditary graph families
• Split graphs and block representations
• Indicated coloring of the Mycielskian of some families of graphs
• Reconfiguration of vertex colouring and forbidden induced subgraphs
• Star coloring of graphs with girth at least five
• Some good characterization results relating to the Kőnig-Egerváry theorem
• Graphs without \(K_ 4\) and well-quasi-ordering
• Bounds for the chromatic number of some \(pK_2\)-free graphs
• The structure of graphs with forbidden induced \(C_4\), \(\overline{C}_4\), \(C_5\), \(S_3\), chair and co-chair
• Graph classes with linear Ramsey numbers
• Non-minimal degree-sequence-forcing triples
• Coloring of a superclass of \(2K_2\)-free graphs

This page was built for publication: Graphs with no induced \(C_ 4\) and \(2K_ 2\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1801686)