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

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

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)

Cites Work

• Title not available (Why is that?)
• Covering all cliques of a graph
• Title not available (Why is that?)
• On Complementary Graphs
• A bound on the chromatic number of graphs without certain induced subgraphs
• Covering the cliques of a graph with vertices

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
• 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
• On the complete width and edge clique cover problems
• 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
• The structure of graphs with forbidden induced $C_4$, $\overline{C}_4$, $C_5$, $S_3$, chair and co-chair
• 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
• 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)