Line perfect graph

A line perfect graph. The edges in each biconnected component are colored black if the component is bipartite, blue if the component is a tetrahedron, and red if the component is a book of triangles.

In graph theory, a line perfect graph is a graph whose line graph is a perfect graph. Equivalently, these are the graphs in which every odd-length simple cycle is a triangle.^[1]

A graph is line perfect if and only if each of its biconnected components is a bipartite graph, the complete graph $K 4$ , or a triangular book $K 1,1, n$ .^[2] Because these three types of biconnected component are all perfect graphs themselves, every line perfect graph is itself perfect.^[1] By similar reasoning, every line perfect graph is a parity graph,^[3] a Meyniel graph,^[4] and a perfectly orderable graph.

Line perfect graphs generalize the bipartite graphs, and share with them the properties that the maximum matching and minimum vertex cover have the same size, and that the chromatic index equals the maximum degree.^[5]

See also

Strangulated graph, a graph in which every peripheral cycle is a triangle

References

^ ^a ^b Trotter, L. E. Jr. (1977), "Line perfect graphs", Mathematical Programming, 12 (2): 255–259, doi:10.1007/BF01593791, MR 0457293
^ Maffray, Frédéric (1992), "Kernels in perfect line-graphs", Journal of Combinatorial Theory, Series B, 55 (1): 1–8, doi:10.1016/0095-8956(92)90028-V, MR 1159851.
^ Grötschel, Martin; Lovász, László; Schrijver, Alexander (1993), Geometric algorithms and combinatorial optimization, Algorithms and Combinatorics, vol. 2 (2nd ed.), Springer-Verlag, Berlin, doi:10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, MR 1261419
^ Wagler, Annegret (2001), "Critical and anticritical edges in perfect graphs", Graph-Theoretic Concepts in Computer Science: 27th International Workshop, WG 2001, Boltenhagen, Germany, June 14–16, 2001, Proceedings, Lecture Notes in Computer Science, vol. 2204, Berlin: Springer, pp. 317–327, doi:10.1007/3-540-45477-2_29, MR 1905643.
^ de Werra, D. (1978), "On line-perfect graphs", Mathematical Programming, 15 (2): 236–238, doi:10.1007/BF01609025, MR 0509968.

Index: pl ar de en es fr it arz nl ja pt ceb sv uk vi war zh ru af ast az bg zh-min-nan bn be ca cs cy da et el eo eu fa gl ko hi hr id he ka la lv lt hu mk ms min no nn ce uz kk ro simple sk sl sr sh fi ta tt th tg azb tr ur zh-yue hy my ace als am an hyw ban bjn map-bms ba be-tarask bcl bpy bar bs br cv nv eml hif fo fy ga gd gu hak ha hsb io ig ilo ia ie os is jv kn ht ku ckb ky mrj lb lij li lmo mai mg ml zh-classical mr xmf mzn cdo mn nap new ne frr oc mhr or as pa pnb ps pms nds crh qu sa sah sco sq scn si sd szl su sw tl shn te bug vec vo wa wuu yi yo diq bat-smg zu lad kbd ang smn ab roa-rup frp arc gn av ay bh bi bo bxr cbk-zam co za dag ary se pdc dv dsb myv ext fur gv gag inh ki glk gan guw xal haw rw kbp pam csb kw km kv koi kg gom ks gcr lo lbe ltg lez nia ln jbo lg mt mi tw mwl mdf mnw nqo fj nah na nds-nl nrm nov om pi pag pap pfl pcd krc kaa ksh rm rue sm sat sc trv stq nso sn cu so srn kab roa-tara tet tpi to chr tum tk tyv udm ug vep fiu-vro vls wo xh zea ty ak bm ch ny ee ff got iu ik kl mad cr pih ami pwn pnt dz rmy rn sg st tn ss ti din chy ts kcg ve

Prefix: a b c d e f g h i j k l m n o p q r s t u v w x y z 0 1 2 3 4 5 6 7 8 9

Portal di Ensiklopedia Dunia

Portal : Agama

Portal : Bahasa

Portal : Biografi

Portal : Budaya

Portal : Elektronika

Portal : Geografi

Portal : Ilmu

Portal : Masyarakat

Portal : Matematika

Portal : Pendidikan

Portal : Politik

Portal : Sejarah

Portal : Seni

Portal : Teknologi

Kembali kehalaman sebelumnya