On a property of the class of n-colorable graphs
From MaRDI portal
Publication:2563166
DOI10.1016/0095-8956(74)90063-XzbMath0269.05103WikidataQ56475007 ScholiaQ56475007MaRDI QIDQ2563166
Publication date: 1974
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Related Items
Linear-sized independent sets in random cographs and increasing subsequences in separable permutations ⋮ Vizing bound for the chromatic number on some graph classes ⋮ Geometry and Combinatorics via Right-Angled Artin Groups ⋮ BOUNDED SEARCH TREE ALGORITHMS FOR PARAMETRIZED COGRAPH DELETION: EFFICIENT BRANCHING RULES BY EXPLOITING STRUCTURES OF SPECIAL GRAPH CLASSES ⋮ A Characterization of b-Perfect Graphs ⋮ The A4-structure of a graph ⋮ Solving the Induced Subgraph Problem in the Randomized Multiparty Simultaneous Messages Model ⋮ Two-colourings that decompose perfect graphs ⋮ The inclusion structure of partially lossy queue monoids and their trace submonoids ⋮ Counting Small Induced Subgraphs Satisfying Monotone Properties ⋮ The signature of chordal graphs and cographs ⋮ On a Class of P 5 -Free Graphs ⋮ P4-Reducible Graphs-Class of Uniquely Tree-Representable Graphs ⋮ Clique-perfectness and balancedness of some graph classes ⋮ A New Class of Brittle Graphs ⋮ Colouring square-free graphs without long induced paths. ⋮ Complete edge-colored permutation graphs ⋮ The Smallest Classes of Binary and Ternary Matroids Closed under Direct Sums and Complements ⋮ On 3‐graphs with no four vertices spanning exactly two edges ⋮ The total co-independent domination number of some graph operations ⋮ Almost controllable graphs and beyond ⋮ Random cographs: Brownian graphon limit and asymptotic degree distribution ⋮ Mixed graphs whose Hermitian adjacency matrices of the second kind have the smallest eigenvalue greater than \(- \frac{3}{2}\) ⋮ The closeness eigenvalues of graphs ⋮ Bounds for the chromatic number of some \(pK_2\)-free graphs ⋮ Classification of non-solvable groups whose power graph is a cograph ⋮ Towards the Erdős-Hajnal conjecture for \(P_5\)-free graphs ⋮ A New Characterization of P 6-Free Graphs ⋮ Vertex-critical \(( P_3 + \ell P_1 )\)-free and vertex-critical (gem, co-gem)-free graphs ⋮ Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs ⋮ Complexity of total dominator coloring in graphs ⋮ Cographs and 1-sums ⋮ \(\boldsymbol{(\alpha, \beta )}\)-Modules in Graphs ⋮ Easily Testable Graph Properties ⋮ Universality of Graphs with Few Triangles and Anti-Triangles ⋮ Cograph editing: Merging modules is equivalent to editing P_4s ⋮ Forbidden subgraphs for graphs with (near) perfect matching to be hamiltonian ⋮ Graphs defined on groups ⋮ Stability of the reverse Blaschke-Santaló inequality for unconditional convex bodies ⋮ Spectral properties of cographs andP5-free graphs ⋮ Obstructions for Three-Coloring and List Three-Coloring $H$-Free Graphs ⋮ Dominator and Total Dominator Colorings in Graphs ⋮ The Trace Monoids in the Queue Monoid and in the Direct Product of Two Free Monoids ⋮ A BOUND FOR THE CHROMATIC NUMBER OF (, GEM)-FREE GRAPHS ⋮ OPEN PACKING NUMBER FOR SOME CLASSES OF PERFECT GRAPHS ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Partial characterizations of circular-arc graphs ⋮ Simplicial Vertices in Graphs with no Induced Four-Edge Path or Four-Edge Antipath, and theH6-Conjecture ⋮ PARTITION REFINEMENT TECHNIQUES: AN INTERESTING ALGORITHMIC TOOL KIT ⋮ Graph Classes and Forbidden Patterns on Three Vertices ⋮ On the \(b\)-dominating coloring of graphs ⋮ On the relationship between NLC-width and linear NLC-width ⋮ On strict strong coloring of graphs ⋮ Defective Coloring on Classes of Perfect Graphs ⋮ On the Nordhaus-Gaddum Problem for the k-Defective Chromatic Number of a Graph ⋮ The Erdös-Hajnal Conjecture-A Survey ⋮ Triangle-free graphs and forbidden subgraphs ⋮ Perfect graphs with no \(P_ 5\) and no \(K_ 5\) ⋮ On the vertex packing problem ⋮ Dichotomizing \(k\)-vertex-critical \(H\)-free graphs for \(H\) of order four ⋮ Slightly triangulated graphs are perfect ⋮ Characterization of \((m,1)\)-transitive and \((3,2)\)-transitive semi- complete directed graphs ⋮ Forbidden induced pairs for perfectness and \(\omega\)-colourability of graphs ⋮ Characterizing forbidden pairs for relative length of longest paths and cycles ⋮ Efficient parallel recognition algorithms of cographs and distance hereditary graphs ⋮ Graphs with at most three distance eigenvalues different from \(-1\) and \(-2\) ⋮ Bull-free Berge graphs are perfect ⋮ Complexity of list coloring problems with a fixed total number of colors ⋮ Mixed graphs with smallest eigenvalue greater than \(- \frac{ \sqrt{ 5} + 1}{ 2} \) ⋮ Recognizing bull-free perfect graphs ⋮ Scheduling of conditional executed jobs on unrelated processors ⋮ Murky graphs ⋮ On semi-\(P_ 4\)-sparse graphs ⋮ An optimal path cover algorithm for cographs ⋮ Locally perfect graphs ⋮ A bipartite analogue of Dilworth's theorem ⋮ Wings and perfect graphs ⋮ Homogeneous sets, clique-separators, critical graphs, and optimal \(\chi\)-binding functions ⋮ Forbidden triples generating a finite set of graphs with minimum degree three ⋮ The setup polyhedron of series-parallel posets ⋮ Chair-free Berge graphs are perfect ⋮ From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats ⋮ A fast parallel algorithm to recognize P4-sparse graphs ⋮ Partitions of graphs into cographs ⋮ Neighborhood covering and independence on \(P_4\)-tidy graphs and tree-cographs ⋮ Characterization of \(P_{6}\)-free graphs ⋮ Forbidden subgraphs and the existence of a spanning tree without small degree stems ⋮ Some perfect coloring properties of graphs ⋮ On the complexity of role colouring planar graphs, trees and cographs ⋮ Excluding pairs of graphs ⋮ The price of connectivity for dominating set: upper bounds and complexity ⋮ On \(r\)-hued colorings of graphs without short induced paths ⋮ On the spectrum of threshold graphs ⋮ Complement reducible graphs ⋮ Classes of perfect graphs ⋮ Completely separable graphs ⋮ Colouring of \((P_3 \cup P_2)\)-free graphs ⋮ Star coloring of certain graph classes ⋮ Primitivity is hereditary for 2-structures ⋮ Partial characterizations of circle graphs ⋮ Lines in hypergraphs ⋮ 3-colorability and forbidden subgraphs. I: Characterizing pairs ⋮ Computing square roots of trivially perfect and threshold graphs ⋮ Square-free perfect graphs. ⋮ Cycle-maximal triangle-free graphs ⋮ A characterization of claw-free \(b\)-perfect graphs ⋮ Short-chorded and perfect graphs ⋮ Minimal volume product near Hanner polytopes ⋮ Dominating cliques in \(P_ 5\)-free graphs ⋮ Dominator colorings in some classes of graphs ⋮ On the \(P_4\)-components of graphs ⋮ Distance eigenvalues of a cograph and their multiplicities ⋮ Graphs with few trivial characteristic ideals ⋮ On a unique tree representation for \(P_ 4\)-extendible graphs ⋮ A tree representation for \(P_ 4\)-sparse graphs ⋮ Partial characterization of graphs having a single large Laplacian eigenvalue ⋮ Coupon coloring of cographs ⋮ Restrictions of graph partition problems. I ⋮ A linear-time recognition algorithm for \(P_{4}\)-reducible graphs ⋮ On the structure of bull-free perfect graphs ⋮ On graphs whose third largest distance eigenvalue dose not exceed \(-1\) ⋮ The graphs with exactly two distance eigenvalues different from \(-1\) and \(-3\) ⋮ Processor optimization for flow graphs ⋮ Complexity and parameterized algorithms for cograph editing ⋮ Competitive graph searches ⋮ Skew partitions in perfect graphs ⋮ Bounding \(\chi \) in terms of \(\omega \) and \(\varDelta \) for some classes of graphs ⋮ Not complementary connected and not CIS \(d\)-graphs form weakly monotone families ⋮ Decomposing complete edge-chromatic graphs and hypergraphs. Revisited ⋮ Infinite versus finite graph domination ⋮ A simple linear time algorithm for cograph recognition ⋮ The Erdős-Hajnal conjecture for rainbow triangles ⋮ A note on a paper by D. Seinsche ⋮ Graph theory (algorithmic, algebraic, and metric problems) ⋮ Chromatic bounds for some classes of \(2 K_2\)-free graphs ⋮ Sandwich problem for \(\varPi\)- and \(\varDelta\)-free multigraphs and its applications to positional games ⋮ Forbidden pairs and the existence of a dominating cycle ⋮ The allocation problem in hardware design ⋮ Transfer flow graphs ⋮ Paired-domination in \(P_{5}\)-free graphs ⋮ Faster algorithms for cograph edge modification problems ⋮ Complete description of forbidden subgraphs in the structural domination problem ⋮ Mixed graphs with smallest eigenvalue greater than \(- \sqrt{3}\) ⋮ Cographs: eigenvalues and Dilworth number ⋮ Bichromatic \(P_{4}\)-composition schemes for perfect orderability ⋮ Colouring square-free graphs without long induced paths ⋮ Base polytopes of series-parallel posets: Linear description and optimization ⋮ Minimal colorings for properly colored subgraphs ⋮ Vertex- and edge-minimal and locally minimal graphs ⋮ On minimal imperfect graphs without induced \(P_5\) ⋮ Sequential colorings and perfect graphs ⋮ The strong perfect graph conjecture: 40 years of attempts, and its resolution ⋮ Algorithms for maximum internal spanning tree problem for some graph classes ⋮ Functions that are read-once on a subset of their inputs ⋮ Generalizing cographs to 2-cographs ⋮ Generalized complementation
Cites Work
- [https://portal.mardi4nfdi.de/wiki/Publication:5675574 Unverschr�nkte Graphen und strategische Spiele in kombinatorischer Form]
- Unnamed Item
