Point partition numbers: perfect graphs

DOI10.1007/S00373-021-02410-WMaRDI QIDQ2115144zbMATH OpenOpenAlexFDO

Authors Justus von Postel, Thomas Schweser, Michael Stiebitz

Publication date 15 March 2022

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2003.04657

zbMATH Keywords

degeneracyperfect graphspoint partition number

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15) Perfect graphs (05C17)

Abstract: Graphs considered in this paper are finite, undirected and without loops, but with multiple edges. For an integer $tgeq1$, denote by $mathcal{MG}_t$ the class of graphs whose maximum multiplicity is at most $t$. A graph $G$ is called strictly $t$-degenerate if every non-empty subgraph $H$ of $G$ contains a vertex $v$ whose degree in $H$ is at most $t-1$. The point partition number $ch{i}_t(G)$ of $G$ is smallest number of colors needed to color the vertices of $G$ so that each vertex receives a color and vertices with the same color induce a strictly $t$-degenerate subgraph of $G$. So $ch{i}_1$ is the chromatic number, and $ch{i}_2$ is known as the point aboricity. The point partition number $ch{i}_t$ with $tgeq1$ was introduced by Lick and White. If $H$ is a simple graph, then $tH$ denotes the graph obtained from $H$ by replacing each edge of $H$ by $t$ parallel edges. Then $omeg{a}_t(G)$ is the largest integer $n$ such that $G$ contains a $t{K}_n$ as a subgraph. Let $G$ be a graph belonging to $mathcal{MG}_t$. Then $omeg{a}_t(G)leqch{i}_t(G)$ and we say that $G$ is $ch{i}_t$-perfect if every induced subgraph $H$ of $G$ satisfies $omeg{a}_t(H)=ch{i}_t(H)$. Based on the Strong Perfect Graph Theorem due to Chudnowsky, Robertson, Seymour and Thomas, we give a characterization of $ch{i}_t$-perfect graphs of $mathcal{MG}_t$ by a set of forbidden induced subgraphs. We also discuss some complexity problems for the class of $ch{i}_t$-critical graphs.

Recommendations

• Point partition numbers: decomposable and indecomposable critical graphs
• scientific article; zbMATH DE number 5077172
• On generalized perfect graphs: Bounded degree and bounded edge perfection
• On claw-free t-perfect graphs
• Perfect graphs

Cites work

• k-Degenerate Graphs
• A characterization of perfect graphs
• Geometric algorithms and combinatorial optimization.
• Hajós and Ore constructions for digraphs
• Minimal imperfect graphs: A simple approach
• Normal hypergraphs and the perfect graph conjecture
• On Partitioning Planar Graphs
• On characterizing game-perfect graphs by forbidden induced subgraphs
• Optimal Vertex Partitions
• Perfect digraphs
• Recognizing Berge graphs
• The ellipsoid method and its consequences in combinatorial optimization
• The strong perfect graph theorem

Cited in

(2)

• scientific article; zbMATH DE number 5896460 (Why is no real title available?)
• Point partition numbers: decomposable and indecomposable critical graphs

This page was built for publication: Point partition numbers: perfect graphs

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