Results 1 to 10 of about 810 (81)
A new characterization of trivially perfect graphs
Electronic Journal of Graph Theory and Applications, 2015 A graph $G$ is \emph{trivially perfect} if for every induced subgraph the cardinality of the largest set of pairwise nonadjacent vertices (the stability number) $\alpha(G)$ equals the number of (maximal) cliques $m(G)$.
Christian Rubio Montiel
doaj +3 more sources
The Chromatic Symmetric Functions of Trivially Perfect Graphs and Cographs [PDF]
Graphs and Combinatorics, 2018 Richard P. Stanley defined the chromatic symmetric function of a simple graph and has conjectured that every tree is determined by its chromatic symmetric function. Recently, Takahiro Hasebe and the author proved that the order quasisymmetric functions, which are analogs of the chromatic symmetric functions, distinguish rooted trees.
Shuhei Tsujie
exaly +4 more sources
Some classes of Trivially Perfect Graphs
Journal of Physics: Conference Series, 2021 Abstract A graph G is supposed to be trivially perfect if, in each induced subgraph H of G, the number of maximal cliques in H equivalents to the size of a maximum independent set in H. Trivially perfect graphs is subclasses of notable perfect graphs and its characterization have numerous continuous applications and it is adequate to ...
G. R. Gandal, R. Mary Jeya Jothi
exaly +2 more sources
Discrete Mathematics, 1978 AbstractAn undirected graph is trivially perfect if for every induced subgraph the stability number equals the number of (maximal) cliques. We characterize the trivially perfect graphs as a proper subclass of the triangulated graphs (thus disproving a claim of Buneman [3]), and we relate them to some well-known classes of perfect graphs.
Martin Charles Golumbic
exaly +3 more sources
Probe threshold and probe trivially perfect graphs
Theoretical Computer Science, 2009 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Van Bang Le, Daniel Bayer
exaly +4 more sources
Computing square roots of trivially perfect and threshold graphs
Discrete Applied Mathematics, 2013 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Martin Milanič
exaly +4 more sources
Defective Coloring on Classes of Perfect Graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2022 In Defective Coloring we are given a graph $G$ and two integers $\chi_d$, $\Delta^*$ and are asked if we can $\chi_d$-color $G$ so that the maximum degree induced by any color class is at most $\Delta^*$.
Rémy Belmonte +2 more
doaj +1 more source
On Restricted Completions of Chordal and Trivially Perfect Graphs
SSRN Electronic Journal, 2022 23 pages, 1 ...
Mitre Costa Dourado +2 more
openaire +3 more sources
Non-Trivial Subring Perfect Codes in Unit Graph of Boolean Rings
Malaysian Journal of Fundamental and Applied Sciences, 2022 The aim of this paper is to investigate the non-trivial subring perfect codes in a unit graph associated with the Boolean rings. We prove a subring perfect code of size , where , in the unit graphs associated with the finite Boolean rings . Moreover, we give a necessary and sufficient condition for a subring of an infinite Boolean ring to be a perfect
Mudaber, Mohammad Hassan +2 more
openaire +2 more sources
On Polar, Trivially Perfect Graphs
International Journal of Computers Communications & Control, 2010 <p>During the last decades, different types of decompositions have been processed in the field of graph theory. In various problems, for example in the construction of recognition algorithms, frequently appears the so-called weakly decomposition of graphs.<br />Polar graphs are a natural extension of some classes of graphs like bipartite ...
Mihai Talmaciu, Elena Nechita
openaire +2 more sources